package DynamicProgramming;

import java.util.Arrays;

public class backpack_complete {

    /**
     * Backpack.
     *
     * @param maxWeight the max weight  背包最大负重
     * @param value     the value   物品对应价值
     * @param weight    the weight  物品对应重量
     */
    public static void backpack(int maxWeight, int[] value, int[] weight){
        int len = value.length;
        int[] dp = new int[maxWeight+1];
        //先遍历物品，再遍历背包
        for (int i = 0; i < len; i++) {
            for (int j = weight[i]; j <= maxWeight; j++) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(Arrays.toString(dp));
    }

    public static void main(String[] args) {

        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
        backpack(bagWeight,value,weight);
    }
}
